# 二分法的多种实现和优劣比较
import time


# 时间统计装饰器
def time_statistics(func):
    def get_time(*args, **kwargs):
        start_time = time.time()
        res = func(*args, **kwargs)
        end_time = time.time()
        print('函数 %s 的执行时间为 %s' % (func.__name__, end_time - start_time))
        return res

    return get_time


# 列表生成式
# start = time.time()
l = [i for i in range(10000000)]
# end = time.time()
# print(end - start)
#
# # for循环生成列表
# start = time.time()
# l2 = []
# for i in range(10000000):
#     l2.append(i)
# end = time.time()
# print(end - start)

target = 999999
sleep_second = 0.000000000001


# 都采用递归写法，比较是否切片方法优劣
# 列表切片写法
def binary_search_slipt(l, target):
    time.sleep(sleep_second)
    if len(l):
        mid = len(l) // 2
        if l[mid] == target:
            return '找到了'
        elif l[mid] < target:
            l_right = l[mid + 1:]
            return binary_search_slipt(l_right, target)
        else:
            l_left = l[:mid]
            return binary_search_slipt(l_left, target)
    else:
        return '未找到'


start_time1 = time.time()
print(binary_search_slipt(l, target))
end_time1 = time.time()
print('函数 %s 的执行时间为 %s' % (binary_search_slipt.__name__, end_time1 - start_time1))

print('-----------------')


# 列表不切片写法
def binary_search_not_split(l, target, start, end):
    time.sleep(sleep_second)
    if start < end:
        mid = (start + end) // 2
        if l[mid] == target:
            return '找到了'
        elif l[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
        return binary_search_not_split(l, target, start, end)
    else:
        return '未找到'


start_time2 = time.time()
print(binary_search_not_split(l, target, 0, len(l) - 1))
end_time2 = time.time()
print('函数 %s 的执行时间为 %s' % (binary_search_not_split.__name__, end_time2 - start_time2))

print('-----------------')


# 采用列表不切片写法比较 是否递归优劣
# 循环写法
@time_statistics
def binary_search_not_recursion(l, target, start, end):
    while True:
        time.sleep(sleep_second)
        if start < end:
            mid = (start + end) // 2
            if l[mid] == target:
                return '找到了'
            elif l[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        else:
            return '未找到'


print(binary_search_not_recursion(l, target, 0, len(l) - 1))

# 有此证明，不切片的方法才是时间和空间最优（因为切片需要更多内存空间）的二分查找实现，不切片同时可以返回得到原本列表中的下标；
# 同时 循环和递归的实现方法时间区别不大
